package com.example.jianzhioffer;

/**
 * Created by Quincy on 2018/9/23.
 * 输入两个链表，找出它们的第一个公共结点。
 */
public class FindFirstCommonNode {

    /**
     * 显然是Y字形链表
     * 原理很简单：就是在较长链表先走两链表长度之差的步数，使较长链表的剩余部分与较短链表等长。
     * */
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int length1 = 0;
        int length2 = 0;

        ListNode temp1 = pHead1;
        ListNode temp2 = pHead2;
        while (pHead1 != null){
            length1++;
            pHead1 = pHead1.next;
        }
        while (pHead2 !=null){
            length2++;
            pHead2 = pHead2.next;
        }

        pHead1 = temp1;
        pHead2 = temp2;
        int diff = 0;
        if (length1 > length2){
            diff = length1 - length2;
            while (diff != 0){
                pHead1 = pHead1.next;
                diff--;
            }
        }else {
            diff = length2 - length1;
            while (diff != 0){
                pHead2 = pHead2.next;
                diff--;
            }
        }
        while (pHead1 != pHead2){
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return pHead1;
    }
}
